{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Phase Kickback"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Phase kickback [[1](#childs),[2](#LinLin),[3](#Wolf)] is an important and highly used primitive in quantum computing, and it deals with kicking the result of a function to the phase of a quantum state so it can be smartly manipulated with constructive and destructive interferences in order to achieve the desired result. Every quantum algortihm can be decomposed into 3 steps: 1)Encoding the data; 2) Manipulating the data; and 3) Extracting the result. The phase kickback primitive is a key step in the manipulaiton of the data that enables the extraction of the result. See the [Deutch-Jozsa](https://github.com/Classiq/classiq-library/blob/main/algorithms/deutsch_jozsa/deutsch_jozsa.ipynb) and [Simon's](https://github.com/Classiq/classiq-library/blob/main/algorithms/simon/simon.ipynb) algortihms for concrete examples of the applications of it.\n",
    "\n",
    "The standard way [[4](#NielsenChuang)] of applying a classical function $f:\\{0,1\\}^n \\rightarrow \\{0,1\\}$ on quantum states is with the oracle model: \n",
    "$\\begin{equation}\n",
    "O_f (|x \\rangle_n|y \\rangle_1) = |x \\rangle_n|y \\oplus f(x) \\rangle_1\n",
    "\\end{equation}$\n",
    "with $|x \\rangle$ and $|y \\rangle$ being the argument and target quantum states respectively, and $\\oplus$ being affition modolu $2$, or the XOR operation. The phase kickback primitive takes the oracle $O_f$ as an input, and performs the follwoing operation:\n",
    "$\\begin{equation}\n",
    "|x \\rangle\\rightarrow (-1)^{f(x)}|x \\rangle\n",
    "\\end{equation}$\n",
    "This can obviously be applied on a superposition of states such that:\n",
    "$\\begin{equation}\n",
    "\\sum_{i=0}^{2^n-1}\\alpha_i|x_i \\rangle\\rightarrow (-1)^{f(x_i)}\\alpha_i|x_i \\rangle\n",
    "\\end{equation}$\n",
    "with $\\alpha_i$ being the amplitude of the $|x_i \\rangle$ state.\n",
    "\n",
    "How this is happening? It's quite simple actually (hence the beuty of it), all needed is to apply the oracle $O_f$ on the state target quantum state $|- \\rangle=\\frac{1}{\\sqrt{2}}|0 \\rangle-\\frac{1}{\\sqrt{2}}|1 \\rangle$ such that:\n",
    "$\\begin{equation}\n",
    "O_f|x \\rangle |- \\rangle = (-1)^{f(x)}|x \\rangle |- \\rangle\n",
    "\\end{equation}$\n",
    "and then effectively the desired transformation $|x \\rangle\\rightarrow (-1)^{f(x)}|x \\rangle$ is achieved. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div style=\"text-align:center;\">\n",
    "    <img src=\"https://docs.classiq.io/resources/phase_kickback_high_level.png\" alt=\"Phase Kickback High Level\" />\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's see how this actually works! (Go to the [Mathemtaical Description](#mathematical-description) for full mathematical description)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Classiq Concepts**\n",
    "* [Within-Apply](https://docs.classiq.io/latest/reference-manual/platform/qmod/language-reference/statements/within-apply/ )\n",
    "* [In-Place XOR](https://docs.classiq.io/latest/reference-manual/platform/qmod/language-reference/statements/numeric-assignment/ )\n",
    "\n",
    "**Related Algorithms**\n",
    "* [Deutch-Jozsa Algorithm](https://github.com/Classiq/classiq-library/blob/main/algorithms/deutsch_jozsa/deutsch_jozsa.ipynb)\n",
    "* [Simon's Algorithm](https://github.com/Classiq/classiq-library/blob/main/algorithms/simon/simon.ipynb)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<details markdown>\n",
    "<summary markdown> NOTE </summary>\n",
    "\n",
    "Sometimes another trick is refered as phase kickback ([video 1](https://www.youtube.com/watch?v=iLcQ-X6QzvU), [video 2](https://www.youtube.com/watch?v=455pmYaZXKw)). This is when applying a unitary $U$ with eigensystem $U| phi \\rangle=e^{i\\phi}|phi\\rangle$ which is controlled by a qubit in the $| + \\rangle=\\frac{1}{\\sqrt{2}}|0\\rangle+\\frac{1}{\\sqrt{2}}|1\\rangle$, the phase of the eigenvalue of $U$ is kicked-back to a relative phase in the controlled qubit:\n",
    "$\\begin{equation}\n",
    "CU| + \\rangle| \\phi \\rangle=\\frac{1}{\\sqrt2}(|0\\rangle| \\phi \\rangle + e^{i\\phi}|1\\rangle| \\phi \\rangle) = \\frac{1}{\\sqrt{2}}(|0\\rangle+e^{i\\phi}|1\\rangle)| \\phi \\rangle\n",
    "\\end{equation}$\n",
    "\n",
    "This is a good trick to know as well, but it is not what is commonly referred to Phase Kickback in the literature [[1](#childs),[2](#LinLin),[3](#Wolf)]\n",
    "</details>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Guided Implementation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In Classiq as in any proper devleoping platform, it is recomended to think and design your code on the functional level in terms of functions. The above figure directs us to what functional building blocks we need to have so now we will implement them one function at a time and then connect them."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "First we start with the **Prepare** $| - \\rangle$ building block implemented with the `prepare_minus` function. It is implemented by sequentially apllying the `X` (NOT) gate that transforms $|0\\rangle$ into $X|0\\rangle=|1\\rangle$, and then applying the Hadmard `H` gate that takes the $|1\\rangle$ state into the desired $H|1\\rangle=| - \\rangle$ state:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div style=\"text-align:center;\">\n",
    "    <img src=\"https://docs.classiq.io/resources/phase_kickback_prepare_minus.gif\" alt=\"Phase Kickback High Level\" />\n",
    "</div>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-05-07T13:28:40.509980Z",
     "iopub.status.busy": "2024-05-07T13:28:40.509504Z",
     "iopub.status.idle": "2024-05-07T13:28:43.317981Z",
     "shell.execute_reply": "2024-05-07T13:28:43.317192Z"
    }
   },
   "outputs": [],
   "source": [
    "from classiq import H, Output, QBit, X, allocate, qfunc\n",
    "\n",
    "\n",
    "@qfunc\n",
    "def prepare_minus(target: Output[QBit]):\n",
    "    allocate(out=target, num_qubits=1)\n",
    "    X(target)\n",
    "    H(target)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Then we need to define the oracle function that implements $O_f| x \\rangle| target \\rangle=| x \\rangle |target \\oplus f(x)\\rangle$. We will implement it for the function $f(x)= (x==0)$, such that the output is $1$ only if the input $x$ equals $0$. That is \n",
    "$\\begin{equation}\n",
    "O_f(| x \\rangle| target \\rangle) = | x \\rangle |target \\oplus (x==0)\\rangle\n",
    "\\end{equation}$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div style=\"text-align:center;\">\n",
    "    <img src=\"https://docs.classiq.io/resources/phase_kickback_oracle_function.gif\" alt=\"Phase Kickback High Level\" />\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "With Classiq the XOR operation ($\\oplus$) is impleneted intuitively with `^=` :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-05-07T13:28:43.324621Z",
     "iopub.status.busy": "2024-05-07T13:28:43.323957Z",
     "iopub.status.idle": "2024-05-07T13:28:43.327908Z",
     "shell.execute_reply": "2024-05-07T13:28:43.327270Z"
    }
   },
   "outputs": [],
   "source": [
    "from classiq import QNum\n",
    "\n",
    "\n",
    "@qfunc\n",
    "def oracle_function(target: QBit, x: QNum):\n",
    "    target ^= x == 0"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we want to combine the two building blocks for preforming the phase kickback. Notice that the we not interested in the $| - \\rangle$ state and its only purpose is for the implementation of $| x \\rangle\\rightarrow (-1)^{f(x)}| x \\rangle$. For such cases (that are common in quantum computing) the QMOD language offers the `Within-Apply` ([read more](https://docs.classiq.io/latest/reference-manual/platform/qmod/language-reference/statements/within-apply/ ) ) statment. Everything we want only for the use of another specific function we apply in the `Within`, and we use it for the specific thing we are interested at in the `Apply`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div style=\"text-align:center;\">\n",
    "    <img src=\"https://docs.classiq.io/resources/phase_kickback_oracle_phase_kickback.gif\" alt=\"Phase Kickback High Level\" />\n",
    "</div>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-05-07T13:28:43.332422Z",
     "iopub.status.busy": "2024-05-07T13:28:43.331903Z",
     "iopub.status.idle": "2024-05-07T13:28:43.341870Z",
     "shell.execute_reply": "2024-05-07T13:28:43.341160Z"
    }
   },
   "outputs": [],
   "source": [
    "from classiq import within_apply\n",
    "\n",
    "\n",
    "@qfunc\n",
    "def oracle_phase_kickback(x: QNum):\n",
    "    target = QBit(\"target\")\n",
    "    within_apply(\n",
    "        compute=lambda: prepare_minus(target), action=lambda: oracle_function(target, x)\n",
    "    )"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<details>\n",
    "\n",
    "<summary>Note! </summary>\n",
    "\n",
    "In the native QMOD syntax in the IDE the following would look like:\n",
    "\n",
    "```\n",
    "qfunc oracle_phase_kickback(x:qnum){\n",
    "  target:qbit;\n",
    "  within{prepare_minus(target);} apply{oracle_function(x,target);}\n",
    "}\n",
    "```\n",
    "which is a bit more intuitive.\n",
    "</details>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we are ready to apply our `oracle_phase_kickback` function. Because we are dealing with quantum algortihms we want to utilize the power of quantum parallelism so we will apply the `oracle_phase_kickback` on a superposition of numbers. Creating a superposition is commonly done with the Hadamrd transform in quantum computing, which is just applying the Hadamrd gate `H` on all the qubits, and it's application on the $|0\\rangle$ state is:\n",
    "$\\begin{equation}\n",
    "H^{\\otimes n}|0\\rangle_n = \\frac{1}{\\sqrt{2^n}}\\sum_{i=0}^{2^n-1}| i \\rangle_n\n",
    "\\end{equation}$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div style=\"text-align:center;\">\n",
    "    <img src=\"https://docs.classiq.io/resources/phase_kickback_hadamrd_tansform.gif\" alt=\"Phase Kickback High Level\" />\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "Therefore our phase kickback primitive is construct of\n",
    "\n",
    "1. Initializing the `qnum` type with $4$ qubits using the `allocate` function such that $| x \\rangle=|0\\rangle$\n",
    "2. Applying the Hadamrd transform on it using the `hadamard_transform` function such that $| x \\rangle = \\frac{1}{\\sqrt{2^n}}\\sum_{i=0}^{2^n-1}| i \\rangle_n$\n",
    "3. Applying the Phase Kickback primitive with the `oracle_phase_kickback` function such that $| x \\rangle = \\frac{1}{\\sqrt{2^n}}\\sum_{i=0}^{2^n-1}(-1)^{i==0}| i \\rangle_n$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-05-07T13:28:43.345452Z",
     "iopub.status.busy": "2024-05-07T13:28:43.344967Z",
     "iopub.status.idle": "2024-05-07T13:28:45.966322Z",
     "shell.execute_reply": "2024-05-07T13:28:45.965655Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Opening: https://platform.classiq.io/circuit/51cc75df-75d3-4f91-ba4c-fc48e41784bc?version=0.41.0.dev39%2B79c8fd0855\n"
     ]
    }
   ],
   "source": [
    "from classiq import create_model, hadamard_transform, show, synthesize\n",
    "\n",
    "\n",
    "@qfunc\n",
    "def main(x: Output[QNum]):\n",
    "    allocate(num_qubits=4, out=x)\n",
    "    hadamard_transform(x)\n",
    "    oracle_phase_kickback(x)\n",
    "\n",
    "\n",
    "qmod = create_model(main)\n",
    "qprog = synthesize(qmod)\n",
    "show(qprog)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div style=\"text-align:center;\">\n",
    "    <img src=\"https://docs.classiq.io/resources/phase_kickback_main.gif\" alt=\"Phase Kickback High Level\" />\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now let's varify that our quantum program actually does what we expect it to do. Remember - we expect to receive a $(-)$ phase only for the state $|0\\rangle$, that is:\n",
    "$\\begin{equation}\n",
    "| x \\rangle = \\frac{1}{\\sqrt{2^4}}(|1\\rangle+| 2 \\rangle+\\dots +| 15 \\rangle-|0\\rangle)\n",
    "\\end{equation}$\n",
    "In order to check this we will use the built-in Classiq state vector simulator from the IDE:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div style=\"text-align:center;\">\n",
    "    <img src=\"https://docs.classiq.io/resources/phase_kickback_result.gif\" alt=\"Phase Kickback High Level\" />\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "And indeed we see that only for the zero state we receive the $(-)$ phase as expected! That's really cool isn't it?\n",
    "Note that in the result we see bit strings of 5 bits rather than just 4 - this includes the `target` qubit measurment that always result 0.\n",
    "\n",
    "To see how this phase kickback is actually implemented in practice see the Deutch-Josza example and Simon's example (TODO links)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Mathematical Description"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Our starting point is the defintion \n",
    "$\\begin{equation}\n",
    "O_f (| x \\rangle_n| y \\rangle_1) = | x \\rangle_n|y \\oplus f(x)\\rangle_1\n",
    "\\end{equation}$\n",
    "for $f:\\{0,1\\}^n \\rightarrow \\{0,1\\}$.\n",
    "\n",
    "Applying $O_f$ on $| x \\rangle| - \\rangle$ results:\n",
    "$\\begin{equation}\n",
    "O_f (| x \\rangle| - \\rangle) = \\frac{1}{\\sqrt{2}}(| x \\rangle |0 \\oplus f(x)\\rangle - | x \\rangle |1 \\oplus f(x)\\rangle)\n",
    "\\end{equation}$\n",
    "\n",
    "The expression $0 \\oplus f(x)$ equals $f(x)$ because $0\\oplus0=0$ and $0\\oplus1=1$.\n",
    "\n",
    "The expression $1\\oplus f(x)$ equals $\\overline{f(x)}$ i.e. `NOT` $f(x)$ since $1\\oplus1=0$ and $1\\oplus0=1$.\n",
    "\n",
    "Therefore:\n",
    "\n",
    "$\\begin{equation}\n",
    "O_f (| x \\rangle| - \\rangle) = | x \\rangle\\frac{1}{\\sqrt{2}}(|f(x)\\rangle - |\\overline{f(x)}\\rangle)\n",
    "\\end{equation}$\n",
    "\n",
    "If $f(x)=0$ the target state is $\\frac{1}{\\sqrt{2}}(|0\\rangle - |1\\rangle) = | - \\rangle = (-1)^{f(x)}| - \\rangle$.\n",
    "\n",
    "If $f(x)=1$ the target state is $\\frac{1}{\\sqrt{2}}(|1\\rangle - |0\\rangle) = -| - \\rangle = = (-1)^{f(x)}| - \\rangle$.\n",
    "\n",
    "Therefore:\n",
    "\n",
    "$\\begin{equation}\n",
    "O_f (| x \\rangle| - \\rangle) = (-1)^{f(x)}| x \\rangle| - \\rangle\n",
    "\\end{equation}$\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## All Code Together"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Python version:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-05-07T13:28:46.004172Z",
     "iopub.status.busy": "2024-05-07T13:28:46.003615Z",
     "iopub.status.idle": "2024-05-07T13:28:48.262514Z",
     "shell.execute_reply": "2024-05-07T13:28:48.261873Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Opening: https://platform.classiq.io/circuit/4915ffcd-0613-479c-b93e-14bdaa8c5d27?version=0.41.0.dev39%2B79c8fd0855\n"
     ]
    }
   ],
   "source": [
    "from classiq import (\n",
    "    H,\n",
    "    Output,\n",
    "    QBit,\n",
    "    QNum,\n",
    "    X,\n",
    "    allocate,\n",
    "    create_model,\n",
    "    hadamard_transform,\n",
    "    qfunc,\n",
    "    show,\n",
    "    synthesize,\n",
    "    within_apply,\n",
    "    write_qmod,\n",
    ")\n",
    "\n",
    "\n",
    "@qfunc\n",
    "def prepare_minus(target: Output[QBit]):\n",
    "    allocate(out=target, num_qubits=1)\n",
    "    X(target)\n",
    "    H(target)\n",
    "\n",
    "\n",
    "@qfunc\n",
    "def oracle_function(target: QBit, x: QNum):\n",
    "    target ^= x == 0\n",
    "\n",
    "\n",
    "@qfunc\n",
    "def oracle_phase_kickback(x: QNum):\n",
    "    target = QBit(\"target\")\n",
    "    within_apply(\n",
    "        compute=lambda: prepare_minus(target), action=lambda: oracle_function(target, x)\n",
    "    )\n",
    "\n",
    "\n",
    "@qfunc\n",
    "def main(x: Output[QNum]):\n",
    "    allocate(num_qubits=4, out=x)\n",
    "    hadamard_transform(x)\n",
    "    oracle_phase_kickback(x)\n",
    "\n",
    "\n",
    "qmod = create_model(main)\n",
    "qprog = synthesize(qmod)\n",
    "show(qprog)\n",
    "\n",
    "write_qmod(qmod, \"phase_kickback\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Native QMOD version:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```\n",
    "// Phase Kickback\n",
    "\n",
    "qfunc prepare_minus(output target:qbit){\n",
    "  allocate<1>(target);\n",
    "  X(target);\n",
    "  H(target);\n",
    "}\n",
    "\n",
    "qfunc oracle_function(x: qnum, target: qbit){\n",
    "  target ^= x==0;\n",
    "}\n",
    "\n",
    "qfunc oracle_phase_kickback(x:qnum){\n",
    "  target:qbit;\n",
    "  within{prepare_minus(target);} apply{oracle_function(x,target);}\n",
    "}\n",
    "\n",
    "qfunc main(output x:qnum){\n",
    "  allocate<4>(x);\n",
    "  hadamard_transform(x);\n",
    "  oracle_phase_kickback(x);\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Refernces "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a id='Childs'>[1]</a>: [Lecture Notes on\n",
    "Quantum Algorithms (Andrew M. Childs)](https://www.cs.umd.edu/~amchilds/qa/qa.pdf)\n",
    "\n",
    "<a id='LinLin'>[2]</a>: [Lecture Notes on\n",
    "Quantum Algorithms for Scientific Computations (Lin Lin)](https://math.berkeley.edu/~linlin/qasc/qasc_notes.pdf)\n",
    "\n",
    "<a id='Wolf'>[3]</a>: [Quantum Computing:\n",
    "Lecture Notes (Ronald de Wolf)](https://homepages.cwi.nl/~rdewolf/qcnotes.pdf)\n",
    "\n",
    "<a id='Nielsen&Chunag'>[4]</a>: [Quantum Computation and Quantum Information (Michael Nielsen and Isaac Chuang)](https://en.wikipedia.org/wiki/Quantum_Computation_and_Quantum_Information)\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.11.4"
  },
  "vscode": {
   "interpreter": {
    "hash": "e992e515f6583afc67b46eeabcda0f30363069fab8b382c7517b274ba7a59477"
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
